0%

最长回文子串

发表于 更新于 分类于

5. 最长回文子串 Longest Palindromic Substring [中等]

题目说明

Leetcode题目链接

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母（大写和/或小写）组成

解题思路

暴力解法

两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。

时间复杂度：O(n^3)

双指针算法

遍历字符串的所有字符，将其作为回文串的中心，使用双指针向两边扩展判断是否对称，从而得到最长的回文串。

在遍历中心点的时候，中心点可以是一个字符或两个字符，比如abcba和abba。

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    string longestPalindrome(string s) {
        string result = "";
        for (int index = 0; index < s.size(); index++)
        {
            auto temp = palindrome_from(s, index, index);
            if (temp.size() > result.size())
            {
                result = temp;
            }

            temp = palindrome_from(s, index, index + 1);
            if (temp.size() > result.size())
            {
                result = temp;
            }
        }
        return result;
    }
private:
    string palindrome_from(const string &s, int left, int right)
    {
        while (left >= 0 && right < s.size())
        {
            if (s[left] != s[right])
            {
                break;
            }
            left--;
            right++;
        }

        int length = (right - 1) - (left + 1) + 1;

        if (length > 0)
        {
            return s.substr(left + 1, length);
        }
        else
        {
            return "";
        }
    }
};

动态规划

  1. 递推公式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // is_palindrome[i][j]: 从下标i到j是否为回文串

    // 1. i == j
    is_palindrome[i][j] = (s[i] == s[j]) = true;

    // 2. j == i + 1
    is_palindrome[i][j] = (s[i] == s[j]);
      
    // 3. j > i + 1
    is_palindrome[i][j] = is_palindrome[i + 1][j - 1] && (s[i] == s[j]);

    汇总一下：

    1
    2
    // total
    is_palindrome[i][j] = (s[i] == s[j]) && ((j <= i + 1) || is_palindrome[i + 1][j - 1]);

  2. 初始值

    is_palindrome应初始化为False。

    1
    std::vector<std::vector<int>> is_palindrome(s.size(), std::vector<int>(s.size(), 0));

  1. 遍历顺序

    由递推公式可知，is_palindrome[i][j]依赖于is_palindrome[i + 1][j - 1]，所以i应该从大到小遍历，j应该从小到大遍历。

    j比i大时无意义，所以j应该由i开始从小到大遍历。

  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    string longestPalindrome(string s) {
        int max_length = 0;
        int start_index = 0;

        vector<vector<int>> is_palindrome(s.size(), vector<int>(s.size(), 0));
        
        for (int i = s.size() - 1; i >= 0; i--)
        {
            for (int j = i; j < s.size(); j++)
            {
                if (s[i] != s[j])
                    continue;

                is_palindrome[i][j] = (j <= i + 1) || is_palindrome[i + 1][j - 1];
                
              	if (!is_palindrome[i][j])
                    continue;

                auto length = j - i + 1;
                if (length >= max_length)
                {
                    start_index = i;
                    max_length = length;
                }
            }
        }

        if (max_length == 0)
        {
            return "";
        }
        else
        {
            return s.substr(start_index, max_length);
        }
    }
};